package com.wellsfargo.bm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class BST {

	public void updateNodeCount(Node cur){
		while(cur.parent!=null){
			if(cur.parent.left==cur)
				cur.parent.leftNodes++;
			else
				cur.parent.rightNodes++;
			cur=cur.parent;
		}
	}
	public Node getBSTfromLevelOrder(int[] A){
		Node root=new Node(A[0]);
		int nP=0;// increments when left or right node is absent.
		List<NodeInfo> q=new ArrayList<NodeInfo>();
		NodeInfo nodeInfo = new NodeInfo(root,Integer.MAX_VALUE,Integer.MIN_VALUE,0);
		q.add(nodeInfo);
		NodeInfo current=nodeInfo;
		while(true){
		    current=q.remove(0);
			int indexLeft=2*current.index +1-nP;
			if(indexLeft>=A.length)
				break;
			if(A[indexLeft]<A[current.index] && A[indexLeft] >current.min){
				current.node.left=new Node(A[indexLeft]);
				current.node.left.parent=current.node;
				current.node.leftNodes++;
				updateNodeCount(current.node);
				q.add(new NodeInfo(current.node.left,A[current.index],current.min,indexLeft));
			}
			else
				nP++;
			int indexRight=2*current.index +2-nP;
			if(indexRight>=A.length)
				break;
			if(A[indexRight]>A[current.index] && A[indexRight] <current.max){
				current.node.right=new Node(A[indexRight]);
				current.node.right.parent=current.node;
				current.node.rightNodes++;
				updateNodeCount(current.node);
				q.add(new NodeInfo(current.node.right,current.max,A[current.index],indexRight));
			}
			else
				nP++;
			
		}
		return root;
	}
	
	public Node getBTfromInandLevel(int[] in, int[] level)
	{
		Map<Integer,Integer> inMap=new HashMap<Integer,Integer>();
		for(int i=0;i<in.length;i++)
			inMap.put(in[i], i);
		Node root=new Node(level[0]);
		int nP=0;// increments when left or right node is absent.
		List<NodeInfo> q=new ArrayList<NodeInfo>();
		NodeInfo nodeInfo = new NodeInfo(root,Integer.MAX_VALUE,Integer.MIN_VALUE,0);
		q.add(nodeInfo);
		NodeInfo current=nodeInfo;
		return root;
	}
	
	public void levelOrderTraversal(Node root){
		
		List<Node> q= new ArrayList<Node>();
		q.add(root);
		int curlevel=1;
		int newlevel=0;
		while(!q.isEmpty()){
			Node cur=q.remove(0);
			System.out.print(cur.value+ " ");
			curlevel--;
			if(cur.left!=null){
				q.add(cur.left);
				newlevel++;
			}
			if(cur.right!=null){
				q.add(cur.right);
				newlevel++;
			}
			if(curlevel==0){
				System.out.println();
				curlevel=newlevel;
				newlevel=0;
			}
		}
	}
	
	public void levelOrderTraversal2(Node root){
		List<Node> q= new ArrayList<Node>();
		q.add(root);
		q.add(null);
		while(q.size()>1){
			Node cur=q.remove(0);
			System.out.print(cur.value+ " ");
			if(cur.left!=null)q.add(cur.left);
			if(cur.right!=null)q.add(cur.right);
			if(q.get(0)==null){
				System.out.println();
				q.remove(0);
				q.add(null);
			}
		}
	}
	/*public Node getBSTfromLevelOrderRecursive(int[] A){
		List<Integer> q=new ArrayList<Integer>();
		List<Node> q2=new ArrayList<Node>();
		return getBSTfromLevelOrderRecursive(A,0,0,q2,q,1,0);
	}
	
	public Node getBSTfromLevelOrderRecursive(int[] A,int curht,int newht, List<Node> q2, List<Integer> q,int num, int nP){
		return root;
	}*/
}
